class Solution
{
public:
    int minExtraChar(string s, vector<string> &dictionary)
    {
        int n = s.size();
        vector<int> dp(n, INT_MAX);

        unordered_set<string> dict(dictionary.begin(), dictionary.end());
        for (int i = 0; i < n; ++i)
        {
            if (dict.count(s.substr(0, i + 1)))
            {
                dp[i] = 0;
            }
            else
            {
                dp[i] = i + 1;
            }
        }

        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                auto part = s.substr(j + 1, i - j);
                if (dict.count(part))
                {
                    dp[i] = min(dp[i], dp[j]);
                }
                else
                {
                    dp[i] = min(dp[i], dp[j] + (int)part.size());
                }
            }
        }
        return dp[n - 1];
    }
};